抖音签名算法的逆向杂谈

前言

我已经来到看雪两年多了，只发过一篇贴子，还不是技术贴。

两年来，我虽然很少在线，但偶尔逛逛也能发现一些有用的文章，解决了我许多疑惑。我今天就把这一周以来研究抖音签名算法的主要心得分享给大家。

初探

抖音的签名算法在libcms.so中，在JNI_Onload中动态注册jni函数。

算法用ollvm混淆了，主要是流程平坦化，流程混淆和运算替换

as,cp算法：

这部分我参考了https://bbs.pediy.com/thread-226931.htm，通过调试对比，很快的就把最新版的as,cp算法弄出来了。所以这部分没什么心得。

mas算法：

这部分我没有找到任何参考文章，是我一步一步调试分析出来得。

先上代码：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
unsigned char ARRAY[0x100];
unsigned int KEY[0x20];
 
unsigned int init = 0;
 
void dump_mem(const char *mem, int len)
{
    for (int i = 0; i < len; ++i)
    {
        unsigned char c = *(unsigned char *)(mem + i);
        const char *fmt = c < 0x10 ? "0x0%X" : "0x%X";
        printf(fmt, c);
        if ((i + 1) % 16 == 0 && (i + 1) < len)
        {
            printf("\n");
        }
        else
        {
            printf(" ");
        }
    }
 
    printf("\n");
}
 
void dump_memToStr(char *str, const char *mem, int len)
{
    for (int i = 0; i < len; ++i)
    {
        unsigned char c = *(unsigned char *)(mem + i);
        const char *fmt = c < 0x10 ? "0%x" : "%x";
        sprintf(str + i * 2, fmt, c);
    }
}
 
int LoadData(const char *fn, void *mem)
{
    FILE *fp = fopen(fn, "rb");
 
    int len = 0;
    fseek(fp, 0, SEEK_END);
    len = ftell(fp);
    rewind(fp);
 
    int rSzie = fread(mem, len, 1, fp);
    fclose(fp);
 
    return rSzie;
}
 
/*
* -----------------------------------------------------------------------------------------------------------------------
* 单个整数处理
*-------------------------------------------------------------------------------------------------------------------------
*/
 
unsigned int encrypt_dword_0(unsigned int d)
{
    unsigned char b[4] = {0};
    for (int i = 0; i < 4; ++i)
    {
        b[i] = *(unsigned char *)((unsigned char *)&d + i);
    }
 
    unsigned int ret = b[0];
    for (int i = 0; i < 3; ++i)
    {
        ret = (ret << 4) + b[i + 1];
    }
 
    return ret;
}
 
unsigned int encrypt_dword_1(unsigned int d)
{
    unsigned int pre = 0;
    unsigned char b[4] = {0};
    for (int i = 0; i < 4; ++i)
    {
        b[i] = *(unsigned char *)((unsigned char *)&d + i);
    }
 
    unsigned int v0, v1, v2, v3, v4;
    for (int index = 0; index < 4; ++index)
    {
        switch (index & 0x1)
        {
        case 0:
            v0 = pre << 7;
            v1 = b[index] ^ v0;
            v2 = pre >> 3;
            v3 = v1 ^ v2;
            pre = pre ^ v3;
            break;
        case 1:
            v0 = pre << 0xB;
            v1 = b[index] ^ v0;
            v2 = pre >> 5;
            v3 = v1 ^ v2;
            v4 = v3 ^ 0xFFFFFFFF;
            pre = pre ^ v4;
            break;
        }
    }
 
    unsigned ret = pre & 0x7FFFFFFF;
    return ret;
}
 
unsigned int encrypt_dword_2(unsigned int d)
{
    unsigned int pre = 0x4E67C6A7;
    unsigned char b[4] = {0};
    for (int i = 0; i < 4; ++i)
    {
        b[i] = *(unsigned char *)((unsigned char *)&d + i);
    }
 
    //printf("b0 = %#x, b1 = %#x, b2 = %#x, b3 =%#x\n",b[0],b[1],b[2],b[3]);
 
    for (int index = 0; index < 4; ++index)
    {
        unsigned int v0 = pre << 5;
        unsigned int v1 = v0 + b[index];
        unsigned int v2 = pre >> 2;
        unsigned int v3 = v1 + v2;
        //printf("v0 = %#x, v1 = %#x, v2 = %#x, v3 = %#x",v0,v1,v2,v3);
 
        pre = pre ^ v3;
        // printf("pre = %#X\n\n\n",pre);
    }
 
    unsigned int ret = pre;
    return ret;
}
 
unsigned int encrypt_dword_3(unsigned int d)
{
    unsigned int v1;
    int v2;
    unsigned int v3;
    unsigned int v4;
 
    v1 = *((unsigned char *)ARRAY + (d >> 24));
    v2 = *((unsigned char *)ARRAY + (unsigned char)d);
    v3 = (*((unsigned char *)ARRAY + ((d >> 16) & 0xFF)) << 16) | (v1 << 24);
    v4 = v3 | (*((unsigned char *)ARRAY + ((unsigned short)d >> 8)) << 8);
    return (((v4 | v2) << 10) | (v3 >> 22)) ^ ((v4 >> 8) | (v2 << 24)) ^ (v4 | v2) ^ (4 * (v4 | v2) | (v1 >> 6)) ^ (((v4 | v2) << 18) | (v4 >> 14));
}
 
/*
* -----------------------------------------------------------------------------------------------------------------------
* 处理索引1-16的数据
*-------------------------------------------------------------------------------------------------------------------------
*/
unsigned int rEndian(unsigned int d)
{
    unsigned char b[4] = {0};
    for (int i = 0; i < 4; ++i)
    {
        b[i] = *(unsigned char *)((unsigned char *)&d + i);
    }
 
    return (b[0] << 24) | (b[1] << 16) | (b[2] << 8) | b[3];
}
 
unsigned char rBit(unsigned char c)
{
    unsigned char tmp = 0;
    unsigned char bit[8] = {0};
 
    for (int i = 0; i < 8; ++i)
    {
        bit[i] = (c >> i) & 0x1;
    }
 
    //dump_mem((const char*)&bit, 8);
 
    for (int i = 0; i < 8; ++i)
    {
        tmp |= (bit[i] << (7 - i)) & 0xFF;
    }
 
    return tmp;
}
 
unsigned int rBit_eachByte(unsigned int d)
{
    unsigned char *C = (unsigned char *)&d;
    unsigned int ret = 0;
 
    for (int index = 0; index < 4; ++index)
    {
        ret |= rBit(C[index]) << (8 * index);
    }
 
    return ret;
}
 
void encrypt_dwordArr_0(unsigned int *D)
{
    unsigned int tD[4] = {0};
    for (int i = 0; i < 4; ++i)
    {
        tD[i] = rEndian(D[i]);
    }
 
    for (int i = 0; i < 32; ++i)
    {
        tD[i % 4] = encrypt_dword_3(tD[(i + 1) % 4] ^ tD[(i + 2) % 4] ^ tD[(i + 3) % 4] ^ KEY[i]) ^ tD[i % 4];
    }
 
    for (int i = 0; i < 4; ++i)
    {
        D[i] = rEndian(tD[3 - i]);
    }
}
 
void encrypt_dwordArr_1(unsigned int *D)
{
    for (int i = 0; i < 4; ++i)
    {
        D[i] = rBit_eachByte(D[i]) ^ rBit_eachByte(encrypt_dword_0(D[(i + 1) % 4])) ^ rBit_eachByte(encrypt_dword_1(D[(i + 2) % 4])) ^ rBit_eachByte(encrypt_dword_2(D[(i + 3) % 4]));
    }
}
 
void encrypt_subBytes(unsigned char *data)
{
    encrypt_dwordArr_0((unsigned int *)data);
    //dump_mem((const char*)data, 16);
 
    encrypt_dwordArr_1((unsigned int *)data);
    //dump_mem((const char*)data, 16);
}
 
/*
* -----------------------------------------------------------------------------------------------------------------------
* 根据as计算mas
*-------------------------------------------------------------------------------------------------------------------------
*/
unsigned char rFourBit(unsigned char c)
{
    return ((c & 0xF) << 4) | ((c >> 4) & 0xF);
}
 
const char *cal_mas_0(const char *as)
{
    unsigned char *mas = (unsigned char *)malloc(27);
    memset(mas, 0, 27);
    mas[0] = 1;
    *(unsigned short *)(mas + 1) = 0x8760; // =(unsigned short)mas
    *(unsigned short *)(mas + 3) = 0x0220; // ???,和getuid有关
 
    memcpy(mas + 5, as, 22);
 
    for (int i = 1; i < 27; ++i)
    {
        mas[i] = rBit(mas[i]);
    }
 
    unsigned char *mas_copy = (unsigned char *)malloc(27);
    memcpy(mas_copy, mas, 27);
    for (int i = 1; i < 17; ++i)
    {
        mas[i] = mas_copy[1 + 16 - i];
    }
 
    encrypt_subBytes(mas + 1);
 
    for (int i = 17; i < 27; ++i)
    {
        mas[i] = mas_copy[17 + 26 - i];
    }
 
    free(mas_copy);
    return mas;
}
 
const char *cal_mas_1(const char *mas)
{
    unsigned char *mas_str = (unsigned char *)malloc(27 * 2 + 1);
    memset(mas_str, 0, 27 * 2 + 1);
 
    dump_memToStr(mas_str, (const char *)mas, 27);
    //printf("%s\n",mas_str);
 
    return mas_str;
}
 
const char *cal_mas(const char *as)
{
    if (!init)
    {
        LoadData("ARRAY.dat", ARRAY);
        LoadData("KEY.dat", KEY);
        init = 1;
    }
 
    return cal_mas_1(cal_mas_0(as));
}

ollvm对这些算法的保护是很有用的，比如像encrypt_dword_0,encrypt_dword_1,encrypt_dword_2这些算法，如果不加ollvm的情况下，估计一天就能全搞定了，但是加上后，可能就要3天了。

刚开始接触ollvm，看到一大堆分支，有点不知所措。不过经过多次调试后，便发现其实ollvm其实是纸老虎。以encrypt_dword_1为例：

分支，单元块虽多，但是有用的也只有5块（其实就只有黄色的三块是重要的）。

那要怎么才能定位到这几块主要的地方呢？

动态调试？这是不可能的，十分耗时间。

正确方法是视觉排除法加直觉。

放大关键部分

结合两张图，可以看出主要块上面的都是一些凭感觉就可以排除，因为他们太小，基本没什么有用运算。通过视觉就可以排除掉60%以上的块了，然后再辅助直觉就可以排除80%的块，然后就可以把剩下的块标注出来，最后剩下的块中基本都至少包含一种有效运算如异或，移位，求和之类的。

再通过下断点调试，这里不是单步调试，而是直接f9。然后观察这些关键运算的操作数。粗略f9跑几遍，有些出现特别多，而操作数又无明显意义（比如运算都是是一个地址加一个常数）的运算，基本可以确定不是关键的。

在剩下的块中，我们要保证输入数据的每一步变化都在这些运算之中，要保证数据变化在掌控之中。最好截图保存运算前后的数据。

如果数据变化在掌控之中，根据截图就可以总结出算法。如：

b0 = 03
b1 = 1B
b2 = 44
b3 = E4
index
 
index=0
v0 = 0 << 7 =0
v1 = 03 xor 0 =03
v2 = 0 >> 03 =0
v3 = 03 xor 0 =03
v4 = 0 xor 03 =03
 
index=1
v5 = 03 << 0B = 1800
v6 = 1800 xor 1B = 181B
v7 = 03 >> 05 = 0
v8 = 181B xor 0 = 181B
v9 = 181B xor FFFFFFFF = FFFFE7E4
v10 = 03 xor FFFFE7E4 = FFFFE7E7
 
index=2
v11 = FFFFE7E7 << 7 = FFF3F380
v12 = FFF3F380 xor 44 = FFF3F3C4
v13 = FFF3E7E7 >> 03 = 1FFFFCFC
v14 = FFF3F3C4 xor 1FFFFCFC = E00C0F38
v15 = FFFFE7E7 xor E00C0F38 = 1FF3E8DF
 
index=3
v16 = 1FF3E8DF << 0b = 9F46F800
v17 = 9F46F800 xor E4 = 9F46F8E4
v18 = 1FF3E8DF >> 05 = 00FF9F46
v19 = 9F46F8E4 xor 00FF9F46 = 9FB967A2
v20 = 9FB967A2 xor FFFFFFFF = 6046985D
v21 = 1FF3E8DF xor 6049985D = 7FB57082
 
ret = 7FB57082 and 7FFFFFFF
 
 
------------------------------------------------------
encrypt(d)
{
    pre=0;
    b[4]={0};
    for(i=0;i<4;++i)
    {
        b[i]=d>>((3-i)*8)&0xFF
    }
 
    for(index=0;index<4;++index)
    {
        switch(index&0x1)
        {
            case 0:
                v0 = pre << 7
                v1 = b[index] xor v0
                v2 = pre >> 3
                v3 = v1 xor v2
                pre = pre xor v3
                break
            case 1:
                v0 = pre << B
                v1 = b[index] xor v0
                v2 = pre >> 5
                v3 = v1 xor v2
                v4 = v3 xor FFFFFFFF
                pre = pre xor v4
        }
    }
 
    ret = pre and 7FFFFFFF
    return ret
}

如果数据变化不在掌控之中，我们可以先大胆猜测一些中间运算，然后验证下，如果能解决最好，不能解决，那就需要在其它可疑块上下断点。

总之，就是要保证数据的来源和去处在掌控之中。

总结

逆向ollvm的最好方法是视觉和直觉排除法。

写到后面发现全文没什么有用的东西，就当作闲聊吧。

最后放上一张验证算法正确的图：

看雪ID：青史无疆 

bbs.pediy.com/user-705599

本文由看雪论坛 青史无疆  原创

转载请注明来自看雪社区

热门技术文章推荐：

戳原文，看看大家都是怎么说的？